package cn.javadog.algorithm.e601_1000;

/**
 * 和可被 K 整除的子数组
 * https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/
 * @author Sprite
 */
public class Algorithm974 {

	public static void main(String[] args) {
		int[] A = {4, 5, 0, -2, -3, 1,4, 5, 0, -2, -3, 1,4, 5, 0, -2, -3, 1,4, 5, 0, -2, -3, 1,4, 5, 0, -2, -3, 1};
		System.out.println(subarraysDivByK(A,5));
		System.out.println(subarraysDivByK2(A,5));
	}

	public static int subarraysDivByK(int[] A, int K) {
		int caluCounter = 0;
		int count = 0;
		if (A.length == 0) return 0;
		// 长度变化
		for (int i = 1; i <= A.length; i++) {
			// 角标
			for (int j = 0; j <= A.length-i; j++) {
				// 子集求和
				int total = 0;
				for (int k = j; k < j+i; k++) {
					total += A[k];
					caluCounter++;
				}
				if (total % K == 0) count++;
			}
		}
		System.out.println("总共计算【" + caluCounter + "】次");
		return count;
	}

	public static int subarraysDivByK2(int[] A, int K) {
		int caluCounter = 0;
		int count = 0;
		if (A.length == 0) return 0;
		// 起始角标
		for (int i = 0; i < A.length; i++) {
			// 子集求和
			int total = 0;
			// 角标
			for (int j = i; j < A.length; j++) {
				total += A[j];
				caluCounter++;
				if (total % K == 0) count++;
			}
		}
		System.out.println("总共计算【" + caluCounter + "】次");
		return count;
	}

	public static int subarraysDivByK3(int[] A, int K) {
		int caluCounter = 0;
		int count = 0;
		if (A.length == 0) return 0;
		// 起始角标
		for (int i = 0; i < A.length; i++) {
			// 子集求和
			int total = 0;
			// 角标
			for (int j = i; j < A.length; j++) {
				total += A[j];
				caluCounter++;
				if (total % K == 0) count++;
			}
		}
		System.out.println("总共计算【" + caluCounter + "】次");
		return count;
	}

}
